package com.sheng.leetcode.year2022.month11.day10;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author liusheng
 * @date 2022/11/10
 *<p>
 * 864. 获取所有钥匙的最短路径<p>
 *<p>
 * 给定一个二维网格 grid ，其中：<p>
 * '.' 代表一个空房间<p>
 * '#' 代表一堵<p>
 * '@' 是起点<p>
 * 小写字母代表钥匙<p>
 * 大写字母代表锁<p>
 * 我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。<p>
 * 我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，<p>
 * 我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。<p>
 * 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。<p>
 * 换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。<p>
 * 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。<p>
 *<p>
 * 示例 1：<p>
 * 输入：grid = ["@.a.#","###.#","b.A.B"]<p>
 * 输出：8<p>
 * 解释：目标是获得所有钥匙，而不是打开所有锁。<p>
 *<p>
 * 示例 2：<p>
 * 输入：grid = ["@..aA","..B#.","....b"]<p>
 * 输出：6<p>
 *<p>
 * 示例 3:<p>
 * 输入: grid = ["@Aa"]<p>
 * 输出: -1<p>
 *<p>
 * 提示：<p>
 * m == grid.length<p>
 * n == grid[i].length<p>
 * 1 <= m, n <= 30<p>
 * grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'<p>
 * 钥匙的数目范围是 [1, 6]<p>
 * 每个钥匙都对应一个 不同 的字母<p>
 * 每个钥匙正好打开一个对应的锁<p>
 */
public class LeetCode0864 {

    @Test
    public void test01() {
        String[] grid = {"@.a.#","###.#","b.A.B"};
//        String[] grid = {"@..aA","..B#.","....b"};
//        String[] grid = {"@Aa"};
        System.out.println(new Solution().shortestPathAllKeys(grid));
    }
}

/**
 * BFS + 状态压缩
 * 一道常规的 BFS 运用题，只不过需要在 BFS 过程中记录收集到的钥匙状态。
 * 利用「钥匙数量不超过 6，并按字母顺序排列」，我们可以使用一个 int 类型二进制数 state 来代指当前收集到钥匙情况：
 * 若 state 的二进制中的第 k 位为 1，代表当前种类编号为 k 的钥匙 已被收集，后续移动若遇到对应的锁则 能通过
 * 若 state 的二进制中的第 k 位为 0，代表当前种类编号为 k 的钥匙 未被收集，后续移动若遇到对应的锁则 无法通过
 * 其中「钥匙种类编号」则按照小写字母先后顺序，从 0 开始进行划分对应：即字符为 a 的钥匙编号为 0，字符为 b 的钥匙编号为 1，字符为 c 的钥匙编号为 2 ...
 * 当使用了这样的「状态压缩」技巧后，我们可以很方便通过「位运算」进行 钥匙检测 和 更新钥匙收集状态：
 * 钥匙检测：(state >> k) & 1，若返回 1 说明第 k 位为 1，当前持有种类编号为 k 的钥匙
 * 更新钥匙收集状态：state |= 1 << k，将 state 的第 k 位设置为 1，代表当前新收集到种类编号为 k 的钥匙
 * 搞明白如何记录当前收集到的钥匙状态后，剩下的则是常规 BFS 过程：
 * 起始遍历一次棋盘，找到起点位置，并将其进行入队，
 * 队列维护的是 (x, y, state) 三元组状态（其中 (x, y) 代表当前所在的棋盘位置，state 代表当前的钥匙收集情况）
 * 同时统计整个棋盘所包含的钥匙数量 cnt，并使用 数组/哈希表 记录到达每个状态所需要消耗的最小步数 step
 * 进行四联通方向的 BFS，转移过程中需要注意「遇到锁时，必须有对应钥匙才能通过」&「遇到钥匙时，需要更新对应的 state 再进行入队」
 * 当 BFS 过程中遇到 state = (1 << cnt) - 1 时，代表所有钥匙均被收集完成，可结束搜索
 *
 * 作者：宫水三叶
 * 链接：<a href="https://leetcode.cn/problems/shortest-path-to-get-all-keys/solutions/1960544/by-ac_oier-5gxc/">...</a>
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Solution {
    static int N = 35, K = 10, INF = 0x3f3f3f3f;
    // (x, y, state) 三元组状态（其中 (x, y) 代表当前所在的棋盘位置，state 代表当前的钥匙收集情况）
    static int[][][] dist = new int[N][N][1 << K];
    // 移动方向
    static int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int shortestPathAllKeys(String[] g) {
        // n 为数组长度，m 为数组中字符串的长度，cnt 为钥匙数量
        int n = g.length, m = g[0].length(), cnt = 0;
        // 创建一个队列 d
        Deque<int[]> d = new ArrayDeque<>();
        // 循环字符串数组中的每一个字符
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 为三元组状态 dist 赋初始值
                Arrays.fill(dist[i][j], INF);
                // 获取对应字符串数组位置的字符 c
                char c = g[i].charAt(j);
                // 如果 c 字符等于 @ 代表找到了起点
                if (c == '@') {
                    // 添加到队列的末尾
                    d.addLast(new int[]{i, j, 0});
                    dist[i][j][0] = 0;
                } else if (c >= 'a' && c <= 'z') {
                    // 如果是小写字母，则代表钥匙，将 cnt 自增
                    cnt++;
                }
            }
        }
        // 队列 d 不为空则进入 while 循环
        while (!d.isEmpty()) {
            // 删除并返回队列中的第一个元素
            int[] info = d.pollFirst();
            int x = info[0], y = info[1], cur = info[2], step = dist[x][y][cur];
            for (int[] di : dirs) {
                int nx = x + di[0], ny = y + di[1];
                // 如果超出了格子所在的范围，则结束当前循环
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                // 获取对应字符
                char c = g[nx].charAt(ny);
                // 如果字符为 # ，则代表遇到了墙，走不通，结束当前循环
                if (c == '#') {
                    continue;
                }
                // 如果遇到了锁，那么判断当前是否有对应锁的钥匙，如果没有则结束当前循环
                if ((c >= 'A' && c <= 'Z') && (cur >> (c - 'A') & 1) == 0) {
                    continue;
                }
                int ncur = cur;
                // 如果当前位置是钥匙，那么将钥匙添加到状态中
                if (c >= 'a' && c <= 'z') {
                    ncur |= 1 << (c - 'a');
                }
                // 判断钥匙是否已经全部拿到，拿到则返回
                if (ncur == (1 << cnt) - 1) {
                    return step + 1;
                }
                // 当前距离是否大于等于之前的距离
                if (step + 1 >= dist[nx][ny][ncur]) {
                    continue;
                }
                // 将当前距离更新到数组中
                dist[nx][ny][ncur] = step + 1;
                // 在队列中添加下一步操作
                d.addLast(new int[]{nx, ny, ncur});
            }
        }
        // 无法拿到全部的钥匙，返回 -1
        return -1;
    }
}
